Packet switching networks are frequently relied on to direct information to specific destinations at high speeds. Such networks are frequently used in digital communications systems, such as telephone switching networks, and in parallel processing applications to communicate between processors.
A self-routing packet switching network is a packet switching network in which switch nodes within the network set themselves based on information contained in the incoming data. Referring to FIG. 1, a typical self-routing packet switching network is designated generally at 10. Incoming packets 12 comprise a header segment 14, which contains the intended destination of the packet 12, and a data segment 16 containing the data to be routed. The first bit of the header segment 14 is an activity bit which tells whether or not the packet is active. Each packet 12 is a serial stream of bits and each packet has the same length.
As shown in FIG. 1, the self-routing packet switching network 10 receives m packets concurrently 3, the packets concurrently entering the network 10 as parallel streams of sequential bits. The network 10 reads the header bits of the header segment 14 of each packet and routes the packet to the output line specified by those bits. Routing in this context is typically defined to include two functions, sorting and expanding. A typical self-routing packet switching network, such as the one shown in FIG. 1, includes both a sorting network 18 and an expanding network 20 to accomplish routing. The sorting network 18 simply orders the packets relative to one another based on the information in the header segment 14 of each packet 12. The expanding network 20 routes sorted packets to an actual physical destination. If some destinations are unused, the expanding network 20 routes the sorted packets around these unused destinations. Destination "2" in FIG. 1, designated at 24, is an example of an unused destination which the expanding network 20 routes packets around.
All self-routing packet switching networks make use of some self-routing algorithm to accomplish the sorting and expanding functions. A self-routing algorithm involves a series of comparisons of incoming bits, after which, if necessary, data lines are interchanged. Referring now to FIG. 2, a simple example of the way a sorting algorithm works is demonstrated by a network 30. The network 30 sorts header data on four input lines 34 into descending order (top to bottom) with six switching elements 41, 42, 43, 44, 45 and 46. A switching element that is schematically represented by an upward arrow within a circle indicates that the data on the two adjacent lines is switched if the data on the bottom line is larger than the data on the top line. Thus, such a switching element ensures that, after the switching element, the top line will contain data that is larger than the data on the bottom line. Conversely, a switching element that is schematically represented by an downward arrow within a circle indicates that the data on the two adjacent lines is switched if the data on the top line is larger than the data on the bottom line. Thus, such a switching element ensures that, after the switching element, the bottom line will contain data that is larger than the data on the top line.
In FIG. 2, exemplary inputs to the network 30, from top to bottom, are 2-1-4-3. A stage in a self-routing packet switching network comprises a vertical column of switching elements. The switching elements 41 and 42 comprise the first stage 51 of the network 30. The switching element 41 allows the data to pass through the adjacent lines without switching because the larger number is already on the top line. The switching element 42, however, interchanges the 4 and the 3 so that the larger data, the 4, is on the bottom line. The middle two inputs cross before a second stage 52, which compares the 2 and 3 (interchanging them), and the 1 and 4 (also interchanging them). This process is repeated at the final stage 53 so that the sorted output is 4-3-2-1.
A frequently used self-routing algorithm is known as the Batcher-Banyan algorithm. In a Batcher-Banyan sorting network handling n concurrent incoming packets, there are (log.sub.2 n)(log.sub.2 n+1)/2 stages of switching elements.
An expanding network is also a complex series of comparisons and interchanges, similar to that of a sorting network. Together, the sorting and expanding networks make up the routing network, also known as the "fabric network." Many different algorithms have been used to make routing decisions, and all are well known to a person having ordinary skill in the art. Any of these algorithms, when implemented, produces a "fabric" of interconnections and ultimately result in the same output. Thus, although some algorithms may be more efficient than others, any fabric implementation of a self-routing algorithm can be used in a self-routing packet switching network.
Most self-routing packet switching networks use the self-routing fabric as a direct bridge between the incoming data and the routed output. A typical direct bridge configuration is shown in FIG. 3. In a direct bridge configuration, incoming data packets 60 are clocked directly through the self-routing fabric 62, comprised of a sorting network 64 and an expanding network 66. All of the data passes through the self-routing fabric 62, each bit of each packet one stage ahead of the following bit.
The direct bridge configuration presents problems in applications handling rapidly arriving data packets. The configuration requires that the switching in the self-routing fabric be done at the same clock speed as the input and the output to the network. Every switching element in the self-routing fabric must operate at this high clock rate. As the target input-output clock frequency of the network approaches the maximum speed of the technology utilized (such as CMOS, ECL, or GaAs), the manufacturing yield for the network is reduced. For any given single-chip network, it becomes increasingly unlikely that every switching element on the chip will be able to operate at the required speed. An exemplary network handling 32 concurrent packets with an 80 Gb/s bandwidth (the bandwidth of a network is the total number of bits per second entering and leaving the network) would have to operate at 2.5 GHz. The number of transistors required would only be on the order of 70,000, but there would be no time margins for these transistors. Thus, an unacceptably poor yield would be expected.
Another exemplary network can achieve the same 80 Gb/s bandwidth by using a slower 625 MHz clock and increasing the number of concurrent packets to 128. However, as the number of concurrent packets being routed increases, the quantity of switching elements required in the self-routing fabric increases rapidly. Thus, the use of 128 concurrent packets requires on the order of 400,000 transistors. Although there are no timing problems with such an architecture, this type of architecture requires an enormous number of transistors and is very costly.
The direct-bridge architecture presents the classic size versus speed trade-off. In high-speed applications, maximizing bandwidth is essential. However, conventional architecture, using a self-routing fabric network as a direct bridge between the input and output of the network, requires either vast numbers of transistors operating at reasonable speeds, or a more reasonable number of transistors straining to operate at high clock speeds. This latter method has the problem of unreasonably low manufacturing yields, due to the fact that the technology used limits the maximum clock rate that can be used.
Thus, there is a need for an architecture of a self-routing packet switching network that can operate internally at a clock speed lower than that of the network input and output, while at the same time not comprising a large additional number of transistors, while maintaining a high bandwidth.